package com.company.algo.niuke;

import com.company.algo.pojo.TreeNode;

import java.util.ArrayList;
import java.util.Stack;

/**
 * 剑指 Offer 34. 二叉树中和为某一值的路径，【做过又不会了】
 * 给定一个二叉树和一个值sum，请找出所有的【根节点到叶子节点】的节点值之和等于sum 的路径，
 */
public class BTSumPath {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    Stack<Integer> path = new Stack<>();

    public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
        recur(root, sum);
        return res;
    }

    void recur(TreeNode root, int target) {
        if (root == null) return;
        target -= root.val;
        path.push(root.val);
        if (target == 0 && root.left == null && root.right == null) res.add(new ArrayList<>(path));
        recur(root.left,target);
        recur(root.right,target);
        path.pop();
    }


    public static void main(String[] args) {
        BTSumPath Main = new BTSumPath();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        System.out.println(Main.pathSum(root, 4));
    }
}
